package q518_change;

public class Solution_1 {
    /**
     * 这也是一个背包问题 但是相较于01背包问题不同点在于
     * 所有的元素是可以重复添加的
     * 所以我们唯一的不同点在于遍历dp容量时——必须采用从小到大的顺序
     * @param amount
     * @param coins
     * @return
     */
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;

        for (int coin : coins) { // 遍历所有我们能用的硬币
            for (int j = coin; j <= amount; j++) { // 遍历我们dp的容量 完全背包是采用正序遍历的
                // 组合数的递推公式
                dp[j] = dp[j] + dp[j - coin]; // 当前的dp[j] = 当前的dp[j] + 当前的dp[j - nums[i]]
            }
        }

        return dp[amount];
    }
}
